package C060;

import java.io.*;
import java.util.Arrays;

/**
 * ClassName: c01
 * Package: C060
 * Description:
 *
 // 最大食物链计数
 // a -> b，代表a在食物链中被b捕食
 // 给定一个有向无环图，返回
 // 这个图中从最初级动物到最顶级捕食者的食物链有几条
 // 测试链接 : https://www.luogu.com.cn/problem/P4017
 // 请同学们务必参考如下代码中关于输入、输出的处理
 // 这是输入输出处理效率很高的写法
 // 提交以下所有代码，把主类名改成Main，可以直接通过
 * @Author BCXJ
 * @Create 2025/11/25 08:52
 * @Version 1.0
 * @Since 1.0
 */
public class c01 {
    public static int MAXN = 5001; // 点数

    public static int MAXM = 500001; // 变数

    public static int MOD = 80112002;

    static int[] head = new int[MAXN];
    static int[] nexts = new int[MAXM];
    static int[] tos = new int[MAXM];

    static int cnt;

    // 队列 - 入度为0的入对列
    static int[] queue = new int[MAXN];
    static int l = 0, r = 0;

    // 入度表
    static int[] indegree = new int[MAXN];

    // 权重数组
    static int[] weights = new int[MAXN];

    // 每次实验的点数和变数
    static int n, m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while(in.nextToken() != StreamTokenizer.TT_EOF) {
            n = (int) in.nval;
            in.nextToken();
            m = (int) in.nval;
            build(n); // 初始化前式链向星
            for (int i = 0, from, to; i < m; i++) {
                in.nextToken();
                from = (int) in.nval;
                in.nextToken();
                to = (int) in.nval;
                addEdge(from, to);
                // 入度统计
                indegree[to] ++;
            }
            // 至此，图和入度表 全都初始化好了, 接下来就是处理数据得到结果
            out.println(ways());
//            System.out.println(ways());
        }
        out.flush();
        out.close();
        br.close();
    }

    // 数据处理
    private static int ways() {
        // 入度为0的点，权重设置为1
        for (int i = 1; i <= n; i++) {
            if(indegree[i] == 0) {
                queue[r ++] = i;
                weights[i] = 1;
            }
        }
        // 走拓扑排序的流程，权重进行累加
        int ans = 0;
        while(l < r) {
            int curNode = queue[l ++];
            int curEdge = head[curNode];
            // 后面不再有边了，结果就出来了
            if (curEdge == 0) {
                // 当前的u节点不再有后续邻居了
                ans = (ans + weights[curNode]) % MOD;
            }
            // 临边遍历
            while(curEdge != 0) {
                if( --indegree[tos[curEdge]] == 0) {
                    queue[r ++] = tos[curEdge];
                }
                weights[tos[curEdge]] = (weights[curNode] + weights[tos[curEdge]]) % MOD;
                curEdge = nexts[curEdge];
            }
        }

        // 返回最高的节点的权重值 即为答案
        return ans;

    }

    // 图加边
    private static void addEdge(int from, int to) {
        nexts[cnt] = head[from];
        head[from] = cnt;
        tos[cnt ++] = to;
    }

    // 初始化前式链向星
    // 节点从1开始，初始化全部设置为0即可
    private static void build(int n) {
        cnt = 1; // 初始化边
        Arrays.fill(head, 0, n + 1, 0); // head数组初始化
        Arrays.fill(indegree, 0, n + 1, 0); // 入度表初始化
        Arrays.fill(weights, 0); // 权重数组初始化
        l = r = 0;
    }
}
